package com.work.daily;

import java.util.Arrays;

/**
 * title:给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
 * 函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
 *
 * solution:二分法
 * time complexity: O(nlogn)
 *
 * link: https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
 *
 * Created by suk on 2020/8/28.
 */
public class T167_TwoSum_01 {

    public static void main(String[] args) {
        int[] numbers = {1 , 2, 3, 4};
        int target = 6;
        System.out.println(Arrays.toString(twoSum(numbers, target)));
    }

    public static int[] twoSum(int[] numbers, int target) {

        int len = numbers.length;

        for (int i = 0; i < len; i++) {
            int left = i + 1;
            int right = len - 1;
            int seek = target - numbers[i];
            while (left <= right) {

                int middle = left + (right - left) / 2;
                if (numbers[middle] == seek)
                    return new int[]{i + 1, middle + 1};

                if (numbers[middle] < seek) {
                    left = middle + 1;
                } else {
                    right = middle - 1;
                }

            }
        }
        return new int[]{-1, -1};
    }
}
